﻿using System;
using System.Collections.Generic;
using System.Linq;

class QuickSort
{
    static void Main()
    {
        Console.Write("Number of elements of array:");
        int arrayLength = int.Parse(Console.ReadLine());
        List<int> array = new List<int>();
        for (int i = 0; i < arrayLength; i++)
        {
            Console.Write("\nInt element a[{0}]:", i);
            array.Add(int.Parse(Console.ReadLine()));
        }
        //List<int> array = new List<int> { 3, 2, 3, 9, 6, 1, 4, 7, 20, 15, 6, 8, 4, 2, 2 };
        //int arrayLength = 15;
        List<int> quicksort = QSort(array);
        
        foreach (var item in quicksort)
        {
            Console.WriteLine(item);
        }
    }

    private static List<int> QSort(List<int> inputArray)
    {
        if (inputArray.Count < 2)
        {
            return inputArray;
        }

        int pivot = inputArray[inputArray.Count / 2];
        inputArray.RemoveAt(inputArray.Count / 2);

        List<int> smallerValues = new List<int>();
        List<int> biggerValues = new List<int>();

        foreach (var item in inputArray)
        {
            if (item > pivot)
            {
                biggerValues.Add(item);
            }
            else
            {
                smallerValues.Add(item);
            }
        }

        smallerValues = (QSort(smallerValues));
        biggerValues = (QSort(biggerValues));

        List<int> result = new List<int>();
        result.AddRange(smallerValues);
        result.Add(pivot);
        result.AddRange(biggerValues);

        return result;
    }
}